package com.review.dp;

import java.util.Arrays;

public class b_1 {
    //换算最少零钱数{2，5，7}  27
    public int coinChange(int[] A, int M) {
        int[] dp = new int[M + 1];//因为要取到dp[M]
        Arrays.fill(dp,M+1);
        dp[0]=0;

        for (int i = 1; i <= M; i++) {
            for (int j = 0; j < A.length; j++) {
                if (i>=A[j]){
                    dp[i]=Math.min(dp[i],dp[i-A[j]]+1);
                }
            }
        }
        if (dp[M]>M){
            return -1;
        }else {
            return dp[M];
        }
    }

    public static void main(String[] args) {
        System.out.println(new b_1().coinChange(new int[]{2, 5, 1}, 11));
    }
}
